/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-node-in-binary-search-tree
   @Language: C++
   @Datetime: 17-03-23 11:16
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param root: The root of the binary search tree.
	 * @param value: Remove the node with given value.
	 * @return: The root of the binary search tree after removal.
	 * See http://eudiwffe.cnblogs.com/p/6207196.html for details
	 * Erase node from a bst - sketch, i' is special for erase 6 (i)
	 *       6            d=6,(3)       f=6           6           d=6,(5)
	 *      / \            / \          / \          / \           /  \
	 *     /   \          /   \        /   \        /   \         /    \
	 *    3    8        p=3    8     d=3    8      3   f=8      f=3     8
	 *   /    / \        /    / \     /    / \     /    / \      / \   / \
	 *  /    /   \      /    /   \   /    /   \   /    /   \    /   \ /   \
	 *  2    7    9    2    7    9   2    7    9  2   d=7  9   2  p=5 7   9
	 *                                                             /
	 *     BST             (i)           (ii)        (iii)        /  (i')
	 *                   erase 6      erase 3      erase 7       4
	 */
	TreeNode* removeNode(TreeNode* root, int val) {
		// write your code here
		TreeNode *f, *p, *d;
		// f is father node
		// p is precursor node
		// d is to be deleted node
		for (f=NULL,d=root; d && d->val!=val;){
			f = d;
			if (d->val < val) d=d->right;
			else d=d->left;
		}
		if (d==NULL) return root;		// cannot find erase node

		if (d->left && d->right){		// deletion has two children
			// find deletion node d's precursor
			for (f=d,p=d->left; p->right; f=p, p=p->right);
			d->val = p->val;			// replace deletion val by precursor
			if (f==d) d->left = p->left;// case (i)
			else f->right = p->left;	// case (i')
		}
		else if (d->left==NULL && d->right==NULL){
			if (d==root) {
				delete root;
				return NULL;			// deletion is single root
			}
			// deletion is leaf
			if (f->left == d) f->left=NULL;
			else if (f->right == d) f->right=NULL;
			delete d;
		}
		else {	// deletion has single child node or branch
			p = (d->left ? d->left : d->right);
			d->val = p->val;
			d->left = p->left;
			d->right = p->right;
			delete p;
		}
		return root;					// return erase node count
	}
};
